#pragma once
#include <map>
using namespace std;

template <typename K, typename V>
class LRUCache
{
    template <typename K, typename V>
    class valueItem
    {
    public:
        K key;
        V value;
        valueItem<K, V>* last;
        valueItem<K, V>* next;
        valueItem(K key, V value) : key(key), value(value) {}
    };
    using node = valueItem<K, V>;

private:
    map<K, node*> allNode;
    node* head = nullptr;
    node* tail = nullptr;
    unsigned int size;

public:
    LRUCache(unsigned int size) : size(size) {}

    V get(K key)
    {
        auto iter = allNode.find(key);
        if (iter == allNode.end())
            throw string("cannot find");
        node* target = iter->second;
        node* next = target->next;
        node* last = target->last;
        //把节点从目前位置取出
        if (next != nullptr)
        {
            next->last = last;
        }
        else
        {
            return target->value; //现在已经是最后一个了，直接返回
        }
        if (last != nullptr)
        {
            last->next = next;
        }
        else
        {
            head = target->next; //现在已经是第一个了，拿走
        }
        //把节点放到最后
        tail->next = target; //现在tail变成倒数第二个
        target->last = tail;
        target->next = nullptr;
        tail = target;
        return target->value;
    }

    void push(K key, V value)
    {
        auto iter = allNode.find(key);
        if (iter == allNode.end())
        {
            node* target = new node(key, value);
            allNode[key] = target;
            if (head == nullptr && tail == nullptr) //其实他俩不会只有一个为nullptr
            {
                head = target;
                tail = target;
            }
            else
            {
                //原先的tail变倒数第二个
                tail->next = target;
                target->last = tail;
                tail = target;
                if (allNode.size() > this->size)
                    removeHead();
            }
        }
        else
        {
            node* n = iter->second;
            n->value = value;
        }
    }

    V removeHead()
    {
        allNode.erase(head->key);
        node* oldHead = head;
        head = head->next;
        head->last = nullptr;

        V ret = oldHead->value;
        delete oldHead;
        return ret;
    }
};
